package 单周赛.history;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 排名：1686
 */
public class 第280场单周赛 {

    public static void main(String[] args) {

    }

    /**
     * 6004. 得到 0 的操作数
     * 给你两个 非负 整数 num1 和 num2 。
     * <p>
     * 每一步 操作 中，如果 num1 >= num2 ，你必须用 num1 减 num2 ；否则，你必须用 num2 减 num1 。
     * <p>
     * 例如，num1 = 5 且 num2 = 4 ，应该用 num1 减 num2 ，因此，得到 num1 = 1 和 num2 = 4 。然而，如果 num1 = 4且 num2 = 5 ，一步操作后，得到 num1 = 4 和 num2 = 1 。
     * 返回使 num1 = 0 或 num2 = 0 的 操作数 。
     * <p>
     * 思路：模拟
     *
     * @param num1
     * @param num2
     * @return
     */
    public static int countOperations(int num1, int num2) {
        int ans = 0;
        while (true) {
            if (num1 == 0 || num2 == 0) {
                break;
            }
            if (num1 >= num2) {
                num1 = num1 - num2;
            } else {
                num2 = num2 - num1;

            }
            ans++;
        }
        return ans;
    }

    /**
     * 6005. 使数组变成交替数组的最少操作数
     * 给你一个下标从 0 开始的数组 nums ，该数组由 n 个正整数组成。
     * <p>
     * 如果满足下述条件，则数组 nums 是一个 交替数组 ：
     * <p>
     * nums[i - 2] == nums[i] ，其中 2 <= i <= n - 1 。
     * nums[i - 1] != nums[i] ，其中 1 <= i <= n - 1 。
     * 在一步 操作 中，你可以选择下标 i 并将 nums[i] 更改 为 任一 正整数。
     * <p>
     * 返回使数组变成交替数组的 最少操作数 。
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/minimum-operations-to-make-the-array-alternating
     * <p>
     * 思路：
     * 求奇数位某个数字出现的最多次数
     * 求偶数位某个数字出现的最多次数
     *
     * @param nums
     * @return
     */
    public static int minimumOperations(int[] nums) {
        int jiMaxKey = 0;
        int jiMaxCount = 0;
        int ouMaxKey = 0;
        int ouMaxCount = 0;
        int jiSecondCount = 0;
        int ouSecondCount = 0;

        Map<Integer, Integer> jiMap = new HashMap<>();
        Map<Integer, Integer> ouMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int cur = nums[i];
            if (i % 2 == 0) {
                ouMap.put(cur, ouMap.getOrDefault(cur, 0) + 1);
                if (ouMap.get(cur) > ouMaxCount) {
                    ouMaxKey = cur;
                    ouMaxCount = ouMap.get(cur);
                }
            } else {
                jiMap.put(cur, jiMap.getOrDefault(cur, 0) + 1);
                if (jiMap.get(cur) > jiMaxCount) {
                    jiMaxKey = cur;
                    jiMaxCount = jiMap.get(cur);
                }
            }
        }
        if (jiMaxKey == ouMaxKey) {
            if (jiMaxCount > ouMaxCount) {
                for (int i = 0; i < nums.length; i++) {
                    int cur = nums[i];
                    if (i % 2 == 0 && cur != ouMaxKey) {
                        if (ouMap.get(cur) > ouSecondCount) {
                            ouSecondCount = Math.max(ouMap.get(cur), ouSecondCount);
                        }
                    }
                }
                return nums.length - jiMaxCount - ouSecondCount;
            } else {
                for (int i = 0; i < nums.length; i++) {
                    int cur = nums[i];
                    if (i % 2 != 0 && cur != jiMaxKey) {
                        if (jiMap.get(cur) > jiSecondCount) {
                            jiSecondCount = Math.max(jiMap.get(cur), jiSecondCount);
                        }
                    }
                }
                return nums.length - ouMaxCount - jiSecondCount;
            }
        }
        return nums.length - jiMaxCount - ouMaxCount;
    }

    /**
     * 6006. 拿出最少数目的魔法豆
     * 给你一个 正 整数数组 beans ，其中每个整数表示一个袋子里装的魔法豆的数目。
     * <p>
     * 请你从每个袋子中 拿出 一些豆子（也可以 不拿出），使得剩下的 非空 袋子中（即 至少 还有 一颗 魔法豆的袋子）魔法豆的数目 相等 。一旦魔法豆从袋子中取出，你不能将它放到任何其他的袋子中。
     * <p>
     * 请你返回你需要拿出魔法豆的 最少数目。
     * <p>
     * 思路
     * 先排序
     * 遍历，以当前袋子为最后每个袋子相等的魔法豆
     * 那么需要去除总共魔法豆sum-后面每个袋子中的魔法豆和当前袋子中魔法豆相等，cur*后面袋子个数（包括当前袋子）
     *
     * @param beans
     * @return
     */
    public static long minimumRemoval(int[] beans) {
        long ans = Long.MAX_VALUE;
        Arrays.sort(beans);
        long sum = 0;
        for (int num : beans) {
            sum += num;
        }
        for (int i = 0; i < beans.length; i++) {
            long curAns = sum - (long) beans[i] * (beans.length - i);
            if (curAns < ans) {
                ans = curAns;
            }
        }
        return ans;
    }

}
